package com.datastructure.string;

/**
 * @author: 临晖
 * @date: 2023/10/16
 * @description:
 */


import java.util.Arrays;

/**
 *
 */
public class Solution05 {


    /**
     *
     * 滑动窗口
     * kmp
     *
     *
     * 给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回  -1 。
     *
     * @param haystack
     * @param needle
     * @return
     */
    public static int strStr(String haystack, String needle) {
        //思路一：
        //如果为空，返回0
        //if (needle == null || needle.equals("")) {
        //    return 0;
        //}
        //int hLen = haystack.length();
        //int nLen = needle.length();
        ////如果小于，直接返回-1
        //if (nLen > hLen) {
        //    return -1;
        //} else if (nLen == hLen) {
        //    if (needle.equals(haystack)) {
        //        return 0;
        //    } else {
        //        return -1;
        //    }
        //}
        //
        ////判断
        ////if (haystack.substring(0, nLen).equals(needle)) {
        ////    return 0;
        ////} else {
        //
        //for (int i = 0; i < hLen - nLen; i++) {
        //    if (needle.equals(haystack.substring(i, i + nLen))) {
        //        return i;
        //    }
        //}
        ////}
        //return -1;

        //思路二 kmp，获取前缀
        int[] next = new int[needle.length()];
        getNext(next, needle);

        int indexH = 0;
        int indexN = 0;

        for (; indexH < haystack.length(); indexH++) {
            if (haystack.charAt(indexH) == needle.charAt(indexN)) {
                indexN++;
                if (indexN == needle.length()) {
                    return indexH - indexN + 1;
                }
            }
            // else if(indexN == 0){
            //    indexN = 0;
            //} else {
            //    indexN = next[indexN - 1];
            //}
            else if (indexN > 0) {
                indexN = next[indexN - 1];
                indexH--;
            }
        }
        return -1;

    }


    /**
     *
     *
     * 前缀表
     *
     * @param next
     * @param s
     */
    public static void getNext(int[] next, String s) {
        int j = 0;
        next[0] = 0;
        for (int i = 1; i < s.length(); i++) {
            //if(j > 0 && s.charAt(i) != s.charAt(j)) {
            //    j = 0;
            //}

            while(j > 0 && s.charAt(i) != s.charAt(j)) {
                j = next[j - 1];
            }

            if (s.charAt(j) == s.charAt(i)) {
                j++;
            }

            next[i] = j;
        }
    }


    /**
     * 判断给定字符串是否由某个字符串循环组成
     * @param s
     * @return
     */
    public boolean repeatedSubstringPattern(String s) {
        //思路一
        //StringBuilder str = new StringBuilder(s + s);
        //str.delete(0, 1);
        //str.delete(str.length() - 1, str.length());
        //return str.toString().contains(s);


        //思路二，kmp
        int size = s.length();
        int[] next = new int[size];
        getNext(next, s);

        //如果出现该规则，那么一定会有最长相等前后缀，因此给定字符串的前缀表不能等于0；
        //其次，如果给定字符串是由重复字符串组成，那么一定会有len % x == 0;
        //因此，当我们使用kmp算法计算出前缀表时，如果有 --- 最长前后相等前后缀，那么该字符串一定是有重复字符串组成，
        //这个时候，在利用前缀表求出x，如果模x等于零，那么就一定是重复字符串；
        if ( next[size - 1] != 0 && size % (size - next[size- 1]) == 0  ) {
            return true;
        }

        return false;

    }





    public static void main(String[] args) {
        //strStr("aabaaabaaac", "aabaaac");
        String s = "abcabcabc";
        int[] next = new int[s.length()];
        getNext(next, s);
        System.out.println(Arrays.toString(next));
    }
}


